﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace GenericLibrary.ExtensionMethods {

    public static class SortedListExtension {

        public static bool BinarySearch<T, U>(this SortedList<T, U> sortedList, T key, out int index) {
            if(sortedList.Count == 0) {
                index = 0;
                return false;
            }

            for(int lowIndex = 0, highIndex = sortedList.Count - 1; true; ) {
                index = (lowIndex + highIndex) / 2;
                int diff = sortedList.Comparer.Compare(key, sortedList.Keys[index]);
                if(diff < 0) {
                    if(index == lowIndex) {
                        return false;
                    }
                    highIndex = index - 1;
                } else if(diff > 0) {
                    if(index == highIndex) {
                        index += 1;
                        return false;
                    }
                    lowIndex = index + 1;
                } else {
                    return true;
                }
            }
        }

        public static int IndexOfLeastGreaterKey<T, U>(this SortedList<T, U> sortedList, T key) {
            try {
                if(sortedList.Comparer.Compare(key, sortedList.Keys[0]) <= 0) {
                    return 0;
                } else if(sortedList.Comparer.Compare(key, sortedList.Keys[sortedList.Count - 1]) == 0) {
                    return sortedList.Count - 1;
                } else if(sortedList.Comparer.Compare(key, sortedList.Keys[sortedList.Count - 1]) > 0) {
                    return -1;
                }
                int i = 0, j = sortedList.Count - 1;
                while(j - i > 1) {
                    int k = (i + j) / 2;
                    int compareResult = sortedList.Comparer.Compare(key, sortedList.Keys[k]);
                    if(compareResult < 0) {
                        j = k;
                    } else if(compareResult > 0) {
                        i = k;
                    } else {
                        return k;
                    }
                }
                return j;
            } catch(Exception) {
                Debug.Assert(false);
                throw;
            }
        }

        public static int IndexOfLeastLesserKey<T, U>(this SortedList<T, U> sortedList, T key) {
            try {
                if(sortedList.Comparer.Compare(key, sortedList.Keys[sortedList.Count - 1]) >= 0) {
                    return sortedList.Count - 1;
                } else if(sortedList.Comparer.Compare(key, sortedList.Keys[0]) == 0) {
                    return 0;
                } else if(sortedList.Comparer.Compare(key, sortedList.Keys[0]) < 0) {
                    return -1;
                }
                int i = 0, j = sortedList.Count - 1;
                while(j - i > 1) {
                    int k = (i + j) / 2;
                    int compareResult = sortedList.Comparer.Compare(key, sortedList.Keys[k]);
                    if(compareResult < 0) {
                        j = k;
                    } else if(compareResult > 0) {
                        i = k;
                    } else {
                        return k;
                    }
                }
                return i;
            } catch(Exception) {
                Debug.Assert(false);
                throw;
            }
        }
    }
}
